NOIP2009 普及组

Actinoi 7月 28, 2019

T1:多项式输出

题目描述

一元次多项式可用如下的表达式表示：

f(x)=a_nxⁿ + a_n−1xⁿ⁻¹ +⋯+a₁x + a₀, a_n≠0

其中，a_ixⁱ称为次项，a_i 称为次项的系数。给出一个一元多项式各项的次数和系数，请按照如下规定的格式要求输出该多项式：

多项式中自变量为，从左到右按照次数递减顺序给出多项式。
多项式中只包含系数不为的项。
如果多项式次项系数为正，则多项式开头不出现“+”号，如果多项式次项系数为负，则多项式以“-”号开头。
对于不是最高次的项，以“+”号或者“-”号连接此项与前一项，分别表示此项系数为正或者系数为负。紧跟一个正整数，表示此项系数的绝对值（如果一个高于次的项，其系数的绝对值为，则无需输出）。如果的指数大于，则接下来紧跟的指数部分的形式为“x^b”，其中为的指数；如果的指数为，则接下来紧跟的指数部分形式为“”；如果的指数为，则仅需输出系数即可。
多项式中，多项式的开头、结尾不含多余的空格。

输入格式

输入共有行

第一行个整数，，表示一元多项式的次数。

第二行有个整数，其中第个整数表示第次项的系数，每两个整数之间用空格隔开。

输出格式

输出共行，按题目所述格式输出多项式。

输入输出样例

输入 #1

5 
100 -1 1 -3 0 10

输出 #1

100x^5-x^4+x^3-3x^2+10

输入 #2

3 
-50 0 0 1

输出 #2

-50x^3+1

说明

NOIP 2009 普及组第一题

对于数据，, 系数

题解：

本题是一道模拟题。我们在读入第一项的系数之后，判断是否为负数，是负数的话那么先输出一个 "-" 号，然后判断是否为，是的话就不输出了，不是的话再判断是否为，是的话就不输出系数了，不是的话输出其绝对值。

接着读入第项，如果等于就啥都不输。不等于的话，如果大于输出 "+"，然后如果其绝对值为的话则不输出系数了，否则输出系数与 x^{n - i + 1}就好辣～

#include <cmath>
#include <iostream>
using namespace std;
int coefficient[101];
int main() {
    int n;
    cin >> n;
    cin >> coefficient[1]; //读入第一项的系数
    if (coefficient[1] <= 0)
        cout << "-";
    if (coefficient[1] != 0) {
        if (abs(coefficient[1]) != 1)
            cout << abs(coefficient[1]);
        cout << "x^" << n;
    }
    for (int i = 2; i <= n; i++) {
        cin >> coefficient[i]; //读入每项的系数
        if (coefficient[i] != 0) {
            if (coefficient[i] > 0)
                cout << "+";
            if (abs(coefficient[i]) != 1)
                cout << coefficient[i];
            if (coefficient[i] == -1)
                cout << "-";
            cout << "x";
            if (n - i + 1 != 1)
                cout << "^" << n - i + 1;
        }
    }
    cin >> coefficient[n + 1];
    if (coefficient[n + 1] != 0) {
        if (coefficient[n + 1] > 0)
            cout << "+";
        cout << coefficient[n + 1] << endl;
    }
    return 0;
}

T2:分数线划定

题目描述

世博会志愿者的选拔工作正在 A 市如火如荼的进行。为了选拔最合适的人才，A市对所有报名的选手进行了笔试，笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取人数的划定，即如果计划录取名志愿者，则面试分数线为排名第（向下取整）名的选手的分数，而最终进入面试的选手为笔试成绩不低于面试分数线的所有选手。

现在就请你编写程序划定面试分数线，并输出所有进入面试的选手的报名号和笔试成绩。

输入格式

第一行，两个整数，中间用一个空格隔开，其中表示报名参加笔试的选手总数，表示计划录取的志愿者人数。输入数据保证向下取整后小于等于。

第二行到第行，每行包括两个整数，中间用一个空格隔开，分别是选手的报名号和该选手的笔试成绩。数据保证选手的报名号各不相同。

输出格式

第一行，有个整数，用一个空格隔开，第一个整数表示面试分数线；第二个整数为进入面试的选手的实际人数。

从第二行开始，每行包含个整数，中间用一个空格隔开，分别表示进入面试的选手的报名号和笔试成绩，按照笔试成绩从高到低输出，如果成绩相同，则按报名号由小到大的顺序输出。

输入输出样例

输入 #1

输出 #1

说明

【样例说明】

，向下取整后为。保证个人进入面试的分数线为，但因为有重分，所以所有成绩大于等于的选手都可以进入面试，故最终有个人进入面试。

NOIP 2009 普及组第二题

题解：

首先，我们先用计算出计划几个人能够进入面试。然后对选手的编号与成绩进行排序，排完序之后，我们找到面试分数线，然后统计有多少人能够进入面试，统计完之后输出面试分数线与进面试的总人数，然后再找一遍，如果当前这个人的分数大于面试分数线，则输出这个人的编号与成绩。

最后附上代码：

#include <iostream>
using namespace std;
int a[5001][3]; //存储选手的报名号和选手的笔试成绩
int main() {
    int n, m;
    cin >> n >> m; //n表示报名参加笔试的选手总数，m表示计划录取的志愿者人数
    int people = m * 1.5; //几个人进入面试
    for (int i = 1; i <= n; i++)
        cin >> a[i][1] >> a[i][2];
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            if (a[i][1] > a[j][1]) { //编号小的在前面
                swap(a[i][1], a[j][1]);
                swap(a[i][2], a[j][2]);
            }
            if (a[i][2] < a[j][2]) { //按成绩进行交换
                swap(a[i][1], a[j][1]);
                swap(a[i][2], a[j][2]);
            }
        }
    }
    int score = a[people][2], sum = 0;
    for (int i = 1; i <= n; i++)
        if (a[i][2] >= score)
            sum++;
    cout << score << " " << sum << endl;
    for (int i = 1; i <= n; i++)
        if (a[i][2] >= score)
            cout << a[i][1] << " " << a[i][2] << endl;
    return 0;
}

T2:细胞分裂

题目描述

博士是 (，生物技术) 领域的知名专家。现在，他正在为一个细胞实验做准备工作：培养细胞样本。博士手里现在有种细胞，编号从，一个第种细胞经过秒钟可以分裂为个同种细胞（为正整数）。现在他需要选取某种细胞的一个放进培养皿，让其自由分裂，进行培养。一段时间以后，再把培养皿中的所有细胞平均分入个试管，形成份样本，用于实验。博士的试管数很大，普通的计算机的基本数据类型无法存储这样大的值，但万幸的是，总可以表示为的次方，即，其中均为基本数据类型可以存储的正整数。注意，整个实验过程中不允许分割单个细胞，比如某个时刻若培养皿中有个细胞，博士可以把它们分入个试管，每试管内个，然后开始实验。但如果培养皿中有个细胞，博士就无法将它们均分入个试管。此时，博士就只能等待一段时间，让细胞们继续分裂，使得其个数可以均分，或是干脆改换另一种细胞培养。为了能让实验尽早开始，博士在选定一种细胞开始培养后，总是在得到的细胞“刚好可以平均分入个试管”时停止细胞培养并开始实验。现在博士希望知道，选择哪种细胞培养，可以使得实验的开始时间最早。

输入输出格式

输入格式

第一行,有一个正整数，代表细胞种数。第二行,有两个正整数，以一个空格隔开，即表示试管的总数 . 第三行有 N 个正整数，第 i 个数 Si表示第 i 种细胞经过 1 秒钟可以分裂成同种细胞的个数。

输出格式

一个整数，表示从开始培养细胞到实验能够开始所经过的最少时间（单位为秒）。如果无论博士选择哪种细胞都不能满足要求，则输出整数。

输入输出样例

输入 #1

1 
2 1 
3s

输出 #1

-1

输入 #2

2
24 1
30 12

输出 #2

说明

【输入输出说明】

经过秒钟，细胞分裂成个，经过秒钟，细胞分裂成个，……，可以看出无论怎么分裂，细胞的个数都是奇数，因此永远不能分入个试管。

【输入输出样例说明】

第种细胞最早在秒后才能均分入个试管，而第种最早在秒后就可以均分（每试管个）。故实验最早可以在秒后开始。

【数据范围】

对于 50%的数据，有。

对于所有的数据，有。

NOIP 2009 普及组第三题

题解：

本题是一道比较有意思的数论题目。因为要可以平均分入个试管我们便可以知道，如果 S_i 符合条件，那么，S_i 在经过一段时间之后，它一定的倍数。因为，所以也一定是的倍数，进而推得包括所有的因子，也包括的所有因子。所以，我们便可以将分解质因数，然后对于每一个，都令 m₁ 的所有因子，如果余数不为，则这个不满足条件。那么，我们设中的某个因子为，则包含个，所以我们将每个的因子都乘上，便得到了每个因子含有几个。

那么，如果这个满足条件应该怎么办呢？我们就来看它的时间是不是最少的。我们将除以的每一个因子，除到不再包括这个因子。我们设这个因子为，中含有个，中含有个，如果的话，则可以将表示为，表示为均为正整数。那么，什么时候包含的的个数大于包含的的个数呢？无疑，再过秒，包含的的个数便大于包含的的个数了。然后，我们统计一下最大的，便是这个想要分到个试管所需要的最小时间了。

最后，我们再找一下所有想要分到个试管所需要的时间中最小的，然后输出就可以啦，如果没有一个 S_i 符合条件，那么便输出结束程序。

最后附上代码：

#include <cmath>
#include <iostream>
using namespace std;
int t[30001]; //存储分解M的质因数的个数
int ym[30001]; //存储M的质因数
int k = 0;
void decomposition(int m) { //分解质因数
    bool r = false; //判断还有没有因数
    int n = sqrt(m) + 1;
    while (m > 0) {
        r = false;
        for (int i = 2; i <= n; i++) {
            if (m % i == 0) {
                if (t[i] == 0) {
                    k++;
                    ym[k] = i;
                }
                t[i]++;
                m /= i;
                r = true;
                break;
            }
        }
        if (r == false) {
            if (t[m] == 0 && m > 1) {
                k++;
                ym[k] = m;
            }
            t[m]++;
            return;
        }
    }
}
int maxx = 0;
int pd(int num) {
    int l = 0;
    for (int i = 1; i <= k; i++) {
        int sum = 0;
        while (!(num % ym[i])) {
            sum++;
            num /= ym[i];
        }
        if (!sum)
            return 0xfffffff;
        int w = 0;
        if (sum < t[ym[i]]) {
            if (t[ym[i]] % sum == 0)
                w = t[ym[i]] / sum;
            else
                w = t[ym[i]] / sum + 1;
        } else
            w = 1;
        l = max (l, w);
    }
    return l;
}
int main() {
    int n, m1, m2; //细胞种数与试管的总数
    cin >> n >> m1 >> m2;
    decomposition(m1);
    for (int i = 1; i <= k; i++)
        t[ym[i]] *= m2;
    int s;
    int ans = 0xfffffff;
    for (int i = 1; i <= n; i++) {
        cin >> s;
        ans = min(ans, pd(s));
    }
    if (ans == 0xfffffff)
        cout << -1;
    else
        cout << ans << endl;
    return 0;
}

T4:道路游戏

题目描述

小新正在玩一个简单的电脑游戏。游戏中有一条环形马路，马路上有个机器人工厂，两个相邻机器人工厂之间由一小段马路连接。小新以某个机器人工厂为起点，按顺时针顺序依次将这个机器人工厂编号为，因为马路是环形的，所以第个机器人工厂和第个机器人工厂是由一段马路连接在一起的。小新将连接机器人工厂的这 n 段马路也编号为，并规定第段马路连接第 i 个机器人工厂和第个机器人工厂（），第段马路连接第个机器人工厂和第个机器人工厂。游戏过程中，每个单位时间内，每段马路上都会出现一些金币，金币的数量会随着时间发生变化，即不同单位时间内同一段马路上出现的金币数量可能是不同的。小新需要机器人的帮助才能收集到马路上的金币。所需的机器人必须在机器人工厂用一些金币来购买，机器人一旦被购买，便会沿着环形马路按顺时针方向一直行走，在每个单位时间内行走一次，即从当前所在的机器人工厂到达相邻的下一个机器人工厂，并将经过的马路上的所有金币收集给小新，例如，小新在（）号机器人工厂购买了一个机器人，这个机器人会从号机器人工厂开始，顺时针在马路上行走，第一次行走会经过号马路，到达号机器人工厂（如果，机器人会到达第个机器人工厂），并将号马路上的所有金币收集给小新。游戏中，环形马路上不能同时存在个或者个以上的机器人，并且每个机器人最多能够在环形马路上行走次。小新购买机器人的同时，需要给这个机器人设定行走次数，行走次数可以为之间的任意整数。当马路上的机器人行走完规定的次数之后会自动消失，小新必须立刻在任意一个机器人工厂中购买一个新的机器人，并给新的机器人设定新的行走次数。以下是游戏的一些补充说明：

游戏从小新第一次购买机器人开始计时。
购买机器人和设定机器人的行走次数是瞬间完成的，不需要花费时间。
购买机器人和机器人行走是两个独立的过程，机器人行走时不能购买机器人，购买完机器人并且设定机器人行走次数之后机器人才能行走。
在同一个机器人工厂购买机器人的花费是相同的，但是在不同机器人工厂购买机器人的花费不一定相同。
购买机器人花费的金币，在游戏结束时再从小新收集的金币中扣除，所以在游戏过程中小新不用担心因金币不足，无法购买机器人而导致游戏无法进行。也因为如此，游戏结束后，收集的金币数量可能为负。现在已知每段马路上每个单位时间内出现的金币数量和在每个机器人工厂购买机器人需要的花费，请你告诉小新，经过个单位时间后，扣除购买机器人的花费，小新最多能收集到多少金币。

输入输出格式

输入格式

第一行个正整数，意义如题目所述。接下来的行，每行有个正整数，每两个整数之间用一个空格隔开，其中第 i 行描述了号马路上每个单位时间内出现的金币数量（金币数量），即第行的第（）个数表示第个单位时间内 i 号马路上出现的金币数量。最后一行，有个整数，每两个整数之间用一个空格隔开，其中第个数表示在号机器人工厂购买机器人需要花费的金币数量（金币数量）。

输出格式

共一行，包含个整数，表示在个单位时间内，扣除购买机器人花费的金币之后，小新最多能收集到多少金币。

输入输出样例

输入 #1

输出 #1

【数据范围】对于 40%的数据，。

对于 90%的数据，。

对于 100%的数据，。

说明

NOIP 2009 普及组第四题

题解：

我们用数组枚举每个单位时间内小新最多能收集到多少金币，用枚举时间，用枚举工厂，用枚举机器人走多长时间，用存储钱数便可以得到：。

~~似乎这不是正解？管他呢，反正都卡过去了（逃~~

#include <iostream>
using namespace std;
int money[1001][1001]; //马路上出现的金币数量
int cost[1001]; //机器人工厂购买机器人需要花费的金币数量
int DP[1001]; //枚举每个单位时间内小新最多能收集到多少金币
int main() {
    int n, m, p; //n个机器人工厂，m为总时间，每个机器人最多能够在环形马路上行走p次
    int q = 0;
    cin >> n >> m >> p;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> money[i][j];
    for (int i = 1; i <= n; i++)
        cin >> cost[i];
    for (int i = 1; i <= m; i++)
        DP[i] = -123456;
    DP[1] = money[1][1] - cost[1];
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++) {
            q = DP[i - 1] - cost[j];
            for (int k = 0; k < p && k + i <= m; k++) {
                int w = k + j > n ? (k + j) % n : k + j;
                q += money[w][i + k];
                DP[k + i] = max(DP[k + i], q);
            }
        }
    cout << DP[m] << endl;
    return 0;
}